package Algorithm.prefix;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. 和为 K 的子数组 https://leetcode.cn/problems/subarray-sum-equals-k
 * 题目简述：给你一个整数数组nums和一个整数k，请你统计并返回数组中和为k的连续子数组的个数 。
 */
public class SubarraySum {

    public static void main(String[] args) {
        new SubarraySum().subarraySum(new int[]{-1,-1,1}, 0);
    }

    /**
     * 思路：连续子数组之和即为一个较长前缀减较短前缀，或者前缀和本身。故可使用一个Map存储当前<前缀和，前缀和个数>，
     * 然后在遍历的过程中，先检查当前前缀和能否和Map中的前缀和构成相减为k并计数，然后将当前前缀和加入Map
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> preMap = new HashMap<>();
        int preSum = 0, count = 0;
        //put(0, 1)用于计算前缀和本身就是k的情况
        preMap.put(0, 1);
        for (int num : nums) {
            preSum += num;
            if (preMap.containsKey(preSum-k))
                count += preMap.get(preSum-k);
            preMap.put(preSum, preMap.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

    public int subarraySum2(int[] nums, int k) {
        if (nums.length == 0) return 0;
        int len = nums.length, count = 0;
        //前缀和数组，preSum[i]为前i个数之和
        int[] preSum = new int[len+1];
        preSum[0] = 0;
        for (int i = 0;i < len;i++) {
            preSum[i+1] = preSum[i] + nums[i];
        }
        for (int left = 0;left < len;left++) {
            for (int right = left;right < len;right++) {
                if (preSum[right+1] - preSum[left] == k)
                    count++;
            }
        }
        return count;
    }
}
